『Extensible Effects An Alternative to Monad Transformers』

#論文メモ

Extensible Effectsについての論文

2013/9/23

著者

大まかな流れ

Abstract

モナド変換子より効率よく柔軟なExtensible EffectというLibraryを設計し、実装した

1 Introduction

関数型言語にMonadが導入された当初はモナド同士の合成の仕方が自明ではなかったが、モナド変換子の登場によりこの辺の問題について調査されるようになった

しかし、モナド変換子にはパフォーマンスや柔軟性の観点でいくつかの課題がある

liftを書くのがめんどい

モナドスタックを積むほどパフォーマンスが悪くなる

#??

モナド変換子の代替としてEDLSがあるが、これにも課題がある

Effectがカプセル化されてない、Effectが型として表現されていないなど

Extensible Effectは、モナド変換子とEDLSの課題を両方とも改善する

2 A Tour of the Extensible Effects Framework

具体例を用いたExtensible Effectの簡単な概説

Eff型やMemberなどのシグネチャの意味

値レベルではmtlとほぼ同じであることの解説など

3 The Extensible Effects Framework

4 Simulating the Full MTL

mtlをsimulateできることを確認

5 Beyond the MTL

mtlではできないことを例を用いて解説

Ext Effの方がmtlより一般的なので。

6 Related Work

7 Conclusions

参考

Extensible Effects はモナド変換子に対する救世主になり得るか？ - konn-san.com

論文読みの補助資料としてめっちゃ助かった

https://nryotaro.dev/posts/extensible_effects/

#WIP

前提とされる知識

モナド変換子

Freeモナド

Typeable型クラス

Abstract

Effectは、clientとeffect handlerの相互作用から発生する

Ext Effを使った実装は、モナド変換子よりも修正が容易

モナド変換子は不可能なこともできる

何 #??

Ext Effは単一のMonadである

clientとhandlerの間のコルーチンのような通信をする

型も良い感じ

Libraryは軽量である

例外追跡もできる

Exception tracking

1 Introduction

関数型プログラミングにMonadが導入された初期は、Monadの合成の仕方はあまりわかっていなかったが、An Abstract View of Programming Languagesの考えに基づいて、様々なMonadの合成方法が調査されてきた

その一つがモナド変換子

問題点がいろいろある

liftを書くのがめんどい

層を重ねるごとにオーバーヘッドがある

一部のモナドを使いたいときも全階層のモナドが実行されてしまうからかmrsekut.icon

モナドスタックは静的に決定されるので、動的に変更できない

IOを頻繁に使うだけの関数でも、毎度liftIOを嵩まないといけないということ？mrsekut.icon

Effectをインターリーブする必要がある

1つのEffectを、もう1つのEffectのスタックにしても目的のセマンティクスが提供されない

これが最も重要らしいが、どういう状況のことを言っているのかわからない #??

5章で具体例ありで解説されるらしいmrsekut.icon

モナド変換子の代替としてEDLSがある

Effectをinteractionとしてモデル化する

意味がわからんmrsekut.icon

Effectは、requestとauthorityに送信する

Effectの例としては、可変変数の更新、例外のthrow, fileの書き込みなど

requestには

実行するactionが記されている

requestの送り元(requester)を再開する継続が含まれている

actionの内容を解釈し、requesterに変わって実行し、

requesterを続行して結果を渡す、か、続行の中断をする

hsのIOの実行が、compilerに任されているのと似ている(?)mrsekut.icon

これには3つの問題がある

globalな外部機関を拡張するのが難しい

Effectがカプセル化されていない

Computational Effectが型に反映されていない

Ext Effは、Freeモナドなどを使ってこれらの問題を解決する

1ページ下の黒丸の箇所がよくわからん #??

Effectを型でちゃんと表現する

Open Unionというものを使う

以下のようなことを行った

mtlと似た構文のExt Effの開発

任意の順序でMonadを組み合わせたり、インターリーブが可能

Libraryなので既存のHaskellプログラムへ導入可能

微妙なバグを引き起こすモナド変換子の表現力の分析

open union typeの実装

Ext Effは、モナド変換子と、EDLSの両方の改善を行っていることになる

2 A Tour of the Extensible Effects Framework

小さな例を使用してinterfaceの紹介する

extensible effects frameworkのtour

interfaceをfigre 1に示す

構文的にはmtlに似ている

全ての計算はEffモナドEff rで表現されている

Effの型シグネチャの理解に書いた

todos

上記メモの??の部分の解決